1. Field of the Invention
The present invention is directed to a method of information interaction that allows users of computers to more effectively browse multidimensional information and understand hidden relationships contained in that information.
2. Related Art
The basic prior art paradigms for user interaction with and finding of information have not changed significantly in the commercial marketplace for years. In a so-called standard browsing paradigm, users follow hyperlinks, i.e., links to other documents embedded within Hypertext Markup Language (HTML) documents, the type of documents found, for example, on the World Wide Web (the xe2x80x9cWebxe2x80x9d). The paradigm is named after the popular term xe2x80x9cbrowsing the Webxe2x80x9d for navigating the Web using browser software, such as Netscape Navigator or Microsoft Explorer. Such browsing typically begins with broad categories and terminates with detailed listings. False starts require users to back up and try again with often confusing navigation mechanisms.
Another such paradigm will be referred to as a query/response paradigm, used for example when searching using an Internet search engine or index, in which users enter a query and then the system responds with an ordered list of results. Often users have to repeat this pattern several times to refine the query.
Examples of each of the above-mentioned interaction paradigms are ubiquitous, particularly on the Internet. FIG. 1 shows an extended directory example of the query/response paradigm from an online service known as PeopleLink (available at the time of filing at: www.peoplelink.com). The intention of PeopleLink is to support users in finding chat partners who may share their interests. The interaction paradigm here is much the same as any other standard query/response problem.
A user begins by specifying a query by choosing from selection tools, or xe2x80x9cwidgetsxe2x80x9d that include drop-down lists and check boxes. Results from the search include a listing of potential partners at reference numeral 2, ordered in this case alphabetically. The listings themselves include links to related information and relevant attribute values, such as whether the individual is online at the time, at reference numeral 3 as well as links to profiles at reference numeral 4 of the listed people.
In this particular example, 3458 matches for the query were found, of which the first 20 are shown at reference numeral 5. There are usually two strategies available for users to proceed from this point: (1) back up and refine the search and/or (2) evaluate the candidate items one by one by flipping through listings pages.
Page flipping and scanning through long lists of result items is tedious and time-consuming, as is query refinement. The problem is magnified when the user is not sure what he or she is looking for. Note that in the directory lookup problem to which the technique of FIG. 1 is directed it is not a trivial matter to determine whether the goal has been reached. It is not at all clear how a user would know if he or she has found a satisfactory chat partner. That determination may depend on what the total set of choices is and how they compare across the attributes available. This type of problem is known as a semi-structured problem, as opposed to a straightforward search of, say, phone numbers by name. Such problems are common in the field of information access, particularly in the shopping domain, and also in many others.
Various information visualization approaches have previously been brought to bear on the information access problem. Such approaches have to date come largely from within academic research communities. One class of prior art solutions to improving on the basic query/response technique has been to seek methods to anticipate search results before issuing the full query, thus speeding the query refinement loop, and improving a query""s probability of success. A first step in this technique is to indicate the size of the item set before users issue a query, thus giving the user a hint about how much he or she needs to restrict the set beyond its initial size before going into an evaluation/browsing mode. An even better technique is to provide instant feedback after each part of a query is formed. Such techniques are the basis of Dynamic Querying, a paradigm developed at the University of Maryland. A description of Dynamic Querying can be found in Shneiderman, B., xe2x80x9cDynamic Queries, Starfield Displays, and the Path to Spotfirexe2x80x9d (1999).
The basic Dynamic Querying technique uses sliders and other widgets to formulate queries; visual feedback is available instantly at a meta-level on the results of the queries in a separate visualization. Early prototypes used a scatterplot to present abstract query results, but later commercializations have used a variety of visualization techniques.
FIG. 2 shows a screendump from a commercial product called Spotfire, from a company founded by one of the students from the University of Maryland, that utilizes the dynamic querying technique. Queries are made with the sliders 10 at right. Results are visualized with the two-dimensional plots and graphs 12 on the left. Based on information available at the company""s website, this product seems to have found its niche in scientific applications. Its sophisticated user interface is not designed to be used by the casual user for, say, shopping, although many earlier prototypes built at the University of Maryland were intended to address more casual users. Shneiderman comments, in the article cited above, on the puzzling fact that these interface ideas have not found easy acceptance within commercial applications such as real estate and movie databases.
It does not appear in any event that these commercial sectors have acknowledged the significance of the interface in the information access problem. One possible factor is that the implementations typically have not been built with mass-market Web browsers in mind. In fact, many of the basic performance goals would be difficult to achieve on the Web without specialized browser plugins.
A group headquartered at the Imperial College of London integrates the query mechanism with the results display using dynamic histograms. The research prototypes Attribute Explorer and Influence Explorer use interactive histograms to explore the relationships of attributes in a given set. These techniques are described in several articles: Tweedie, L. A., Spence, R., Dawkes, H., and Su, H. (1996) xe2x80x9cExternalizing Abstract Mathematical Modelsxe2x80x9d, Proceedings of CHI xe2x80x296, Vancouver, Canada, ACM Press, pp. 406-412; and Tweedie, L. A., R. Spence, D. Williams, and R. Bhogal (1994) xe2x80x9cThe Attribute Explorerxe2x80x9d, Video Proceedings and Conference Companion of CHI xe2x80x294, New York, ACM Press, pp. 435-436.
FIG. 3 shows how Attribute Explorer makes use of synchronized interactive histograms to make queries and exhibit attribute relationships in a data set. This example domain relates to housing. In the example shown in the figure, there are three attributes: price 20, distance from a certain location 21, and size of the garden (lawn) 22. Histograms are used in all cases to show the distribution of the data across these attributes. A user can restrict an attribute""s value range by interacting with the sliders at the bottom of the windows; results are painted back onto all the displays by coloring the histograms.
Interactive histograms have the advantage of showing aggregate relationships clearly. The display is by value rather than by item. That is, a value range is plotted on an axis and the number of items that fall into that value is plotted on the second axis to yield a histogram. This is done for each attribute dimension.
In the area of evaluation of result items, many existing sites have turned to methods for direct attribute comparison through tables. The more advanced of these may allow users to sort the tables interactively by different attributes. A good example of a shopping site that has some of these table comparison features is Netmarket, whose website, at the time of filing, is http://www.netmarket.com.
Table layouts are appropriate when the number of items and attributes is relatively small. A table view for a set of hundreds of items and dozens of attributes would obviously be ineffective. Viewing alone would be difficult because the table size would greatly exceed screen real estate, requiring extensive scrolling. More significantly, users cannot be expected to grasp the complex relationships and trade-offs between items and their attribute values in a large table without some additional help. Sorting with large tables may support the task of finding a known target or selecting an unknown item if criteria are simple. It is not difficult with such methods to find the least expensive item, for instance, but many selection and shopping decisions are much more complex and may require understanding the relationship of price to other attributes.
A more advanced table-based visualization tool has been announced from InXight, a Xerox Parc spin-off. It is a commercialization of research conducted at Xerox Parc on a tool called TableLens. It ultimately may offer an interesting avenue for applications such as shopping, but so far it is directed to sophisticated users in business intelligence domains.
The vast majority of academic prototypes and commercial tools in the visualization arena are directed to sophisticated users engaged in scientific pursuits or numerical business analysis. There are hundreds of such products on the market. One example is MineSet(trademark) from Silicon Graphics, which takes the approach of seeking a projection of multidimensional data onto an absolute positioning in 3- (or 2-) dimensional space. Information from other dimensions can then take the form of decorations, such as color, that can be painted into the basic visualization.
A technique from the data visualization community called Parallel Coordinates presents each information dimension separately but in parallel. See Inselberg, A. (1997) xe2x80x9cMultidimensional Detective.xe2x80x9d Proceedings of IEEE Information Visualization xe2x80x297, pp. 100-107; and Inselberg, A., and Dimsdale, B. (1990) xe2x80x9cParallel Coordinates: A Tool For Visualizing Multi-dimensional Geometry.xe2x80x9d Visualization xe2x80x290, San Francisco, Calif. 1990, pp. 361-370.
In this technique, each dimension is ordered and plotted. Lines are drawn across the dimensions in order to show relationships. The above technique relies on a static visual presentation with pattern recognition and is not interactive.
While some data visualization tools address the need to understand global information dimensions and their relationships, most prior art data visualization tools are not for the casual user nor are they targeted to tasks such as shopping on the Internet. Such tasks typically require not just understanding statistical correlations across multiple attributes, but also the need to jump back and forth from a global context to the details of individual items. The shopping task, along with information seeking dialogs in general, is characterized by the need to whittle down a large initial set of choices to just a few.
Further, while both the hyperlink and query/response techniques may be effective if the user knows what he or she is looking for, they can be unwieldy as discussed above, and if the user does not have a definite idea what he or she is looking for, are not conducive to obtaining useful results. While the information sciences have been exploring improvements to the internals of query matching for decades, the user interaction paradigm deployed commercially has remained largely unchanged.
Thus there is a need for developing techniques for multidimensional visualization that are easy to use and which integrate aggregate attribute information with browsing of individual items.
In consideration of the above problems with the prior art, in accordance with a first aspect of the present invention, there is provided a system for browsing multidimensional information. The system comprises: a digital data storage circuit that stores the multidimensional information in a database; a digital logic circuit operable to import, manipulate and output the multidimensional information in the database in accordance with a mapping model that maps each dimension of multidimensional information space to a location in abstract physical space; and a user interface that interactively accepts input from a user and, using the mapping model, renders a graphical representation of the multidimensional space. The graphical representation is responsive to input of user-initiated restrictions on the multidimensional information space by effecting corresponding visible manifestations in the graphical representation.
In accordance with one aspect of the present invention, there is provided a system for browsing multidimensional information. The system comprises: a digital data storage circuit that stores the multidimensional information in a database; a digital logic circuit operable to import, manipulate and output the multidimensional information in the database in accordance with a mapping model that maps each dimension of multidimensional information space to a location in abstract physical space; and a user interface that interactively accepts input from a user and, using the mapping model, renders a graphical representation of the multidimensional information space. The graphical representation is responsive to input of user-initiated restrictions on the multidimensional information space by effecting corresponding visible manifestations in the graphical representation.
In accordance with another aspect of the present invention, there is provided a method for browsing multidimensional information in a database, the method for use on an apparatus having a digital logic circuit operable to import, manipulate and output the multidimensional information in the database. The method comprises: (a) mapping each dimension of multidimensional information space to a location in abstract physical space; and (b) interactively accepting input from a user and, using the mapping, rendering a graphical representation of the multidimensional information space. The graphical representation is responsive to input of user-initiated restrictions on the multidimensional information space by effecting corresponding visible manifestations in the graphical representation.
In accordance with yet another aspect of the present invention, there is provided an apparatus for browsing multidimensional information in a database. The apparatus comprises: digital logic means for importing, manipulating and outputting the multidimensional information in the database in accordance with a mapping of each dimension of multidimensional information space to a location in abstract physical space; and user interface means for interactively accepting input from a user and, using the mapping, rendering a graphical representation of the multidimensional information space. The graphical representation is responsive to input of user-initiated restrictions on the multidimensional information space by effecting corresponding visible manifestations in the graphical representation.
In accordance with still another aspect of the present invention, there is provided a computer-readable medium storing code executable by a processor-controlled apparatus to perform a method for browsing multidimensional information in a database, the apparatus having a digital logic circuit operable to import, manipulate and output the multidimensional information in the database. The method comprises: (a) mapping each dimension of multidimensional information space to a location in abstract physical space; and (b) interactively accepting input from a user and, using the mapping, rendering a graphical representation of the multidimensional information space. The graphical representation is responsive to input of user-initiated restrictions on the multidimensional information space by effecting corresponding visible manifestations in the graphical representation.
In accordance with another aspect of the present invention, there is provided a system for browsing multidimensional information available on a network. The system comprises: a digital logic circuit operable to import from the network, manipulate and output to the network the multidimensional information in accordance with a mapping model that maps each dimension of multidimensional information space to a location in abstract physical space; and a user interface that interactively accepts input from a user and, using the mapping model, renders a graphical representation of the multidimensional information space. The graphical representation is responsive to input of user-initiated restrictions on the multidimensional information space by effecting corresponding visible manifestations in the graphical representation.
In accordance with another aspect of the present invention, there is provided a system for browsing multidimensional information available on the Internet. The system comprises: a digital logic circuit operable to import from the Internet, manipulate and output to the Internet the multidimensional information in accordance with a mapping model that maps each dimension of multidimensional information space to a location in abstract physical space; and a user interface that interactively accepts input from a user and, using the mapping model, renders a graphical representation of the multidimensional information space. The graphical representation is responsive to input of user-initiated restrictions on the multidimensional information space by effecting corresponding visible manifestations in the graphical representation.